package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC809 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int expressiveWords(String s, String[] words) {
            List<Object[]> target = countWord(s);
            int ans = 0;
            for (String word : words) {
                List<Object[]> list = countWord(word);
                // 如果两段不相等，跳过
                if (list.size() != target.size())
                    continue;
                int i = 0;
                for (; i < target.size(); i++) {
                    // 该段字符不同，break
                    if ((char) target.get(i)[0] != (char) list.get(i)[0])
                        break;
                    int t1 = (int) target.get(i)[1];
                    int t2 = (int) list.get(i)[1];
                    // 如果该段字母出现的次数比s还要大，无法扩张，若该条件不满足，此时t1 >= t2，
                    // 此时若两者不相等且t1小于3，则s无法通过word扩张得到
                    if (t1 < t2 || (t1 != t2 && t1 < 3))
                        break;
                }
                // 如果i走到了最后，则word能够扩张得到s
                if (i == target.size())
                    ans++;
            }
            return ans;
        }

        // 统计字符串每段字母及其出现的次数
        // List中存储的是长度为2的数组,o[0]是该段的字母，o[1]是该段该字母出现的频次
        List<Object[]> countWord(String s) {
            List<Object[]> list = new ArrayList<>();
            int i = 0;
            while (i < s.length()) {
                char c = s.charAt(i);
                int count = 0;
                while (i < s.length() && c == s.charAt(i)) {
                    count++;
                    i++;
                }
                list.add(new Object[]{c, count});
            }
            return list;
        }
    }


    class Solution_Less_Consider {
        public int expressiveWords(String s, String[] words) {
            LinkedHashMap<Character, Integer> standardMap = new LinkedHashMap<>();
            char before = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != before) before = s.charAt(i);
                standardMap.put(before, standardMap.getOrDefault(before, 0) + 1);
            }

            int res = 0;
            LinkedList<Character> standardKeyList = new LinkedList<>(standardMap.keySet());
            for (String word : words) {
                int curSameStartPos = 0, curMatchCharPos = 0;
                boolean curCan = true;

                for (int i = 1; i < word.length(); i++) {
                    if (word.charAt(curSameStartPos) != word.charAt(i)) {
                        // 新字符串出现了，开始判断上一个字符
                        if (curMatchCharPos >= standardKeyList.size() || word.charAt(curSameStartPos) != standardKeyList.get(curMatchCharPos)) {
                            curCan = false;
                            break;
                        }

                        int standardCharCnt = standardMap.get(standardKeyList.get(curMatchCharPos));
                        int curMatchCharCnt = i - curSameStartPos;
                        if (standardCharCnt == curMatchCharCnt || standardCharCnt - curMatchCharCnt >= 2) {
                            curSameStartPos = i;
                            curMatchCharPos++;
                        } else {
                            curCan = false;
                            break;
                        }
                    }
                }

                if (!curCan) continue;
                if (word.charAt(curSameStartPos) != standardKeyList.get(curMatchCharPos)) continue;
                int standardCharCnt = standardMap.get(standardKeyList.get(curMatchCharPos));
                int curMatchCharCnt = word.length() - curSameStartPos;
                if (!(standardCharCnt == curMatchCharCnt || standardCharCnt - curMatchCharCnt >= 2)) continue;
                if (curMatchCharPos != standardKeyList.size() - 1) continue;

                res++;
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        String s = "heeellooo";
//        String[] arr = {"heeelloooworld", "hi", "helo"};

        String s = "sass";
        String[] arr = {"sa", "hi", "helo"};

        System.out.println(solution.expressiveWords(s, arr));
    }

    public static void main(String[] args) throws Exception {
        LC809 an = new LC809();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
